Not applicable
This invention is in the field of telecommunications, and is more specifically directed to flow control in asynchronous transfer mode (ATM) communications.
In the field of digital communications, whether applied to voice, video, or data communication, various techniques have been developed for routing messages among nodes connected in a network. One such approach is referred to as packet-based data communications, in which certain network nodes operate as concentrators to receive portions of messages, referred to as packets, from the sending units. These packets may be stored at the concentrator, and are then routed to a destination concentrator to which the receiving unit indicated by the packet address is coupled. The size of the packet refers to the maximum upper limit of information that can be communicated between concentrators (i.e., between the store and forward nodes), and is typically a portion of a message or file. Each packet includes header information relating to the source network address and destination network address, which permits proper routing of the message packet. Packet switching with short length packets ensures that routing paths are not unduly dominated by long individual messages, and thus reduces transmission delay in the store-and-forward nodes. Packet-based data communications technology has enabled communications to be carried out at high data rates, up to and exceeding hundreds of megabits per second.
A well-known example of a fast packet switching protocol, which combines the efficiency of packet switching with the predictability of circuit switching, is Asynchronous Transfer Mode (generally referred to as xe2x80x9cATMxe2x80x9d), in which packet lengths and organization are fixed, regardless of message length or data type (i.e., voice, data, or video). The fixed packets according to the ATM protocol are referred to as xe2x80x9ccellsxe2x80x9d, and each ATM cell is composed of fifty-three bytes, five of which are dedicated to the header and the remaining forty-eight of which serve as the payload. According to this protocol, larger packets are made up of a number of fixed-length ATM cells. The fixed-size cell format enables ATM cell switching to be implemented in hardware, as opposed to software, resulting in transmission speeds in the gigabits-per-second range. In addition, the switching of cells rather than packets permits scalable user access to the network, from a few Mbps to several Gbps, as appropriate to the application. The asynchronous nature of the transmission permits ATM cells to be used in transmitting delay-tolerant data traffic intermixed with time-sensitive traffic like voice and video over the same backbone facility. To more efficiently utilize the bandwidth for these various applications, traffic management techniques are now employed which give priority to time-sensitive traffic relative to delay-tolerant traffic.
Closed loop traffic management involves the use of feedback signals between two network nodes to govern the data rates of channels, with a goal of improving the efficiency of bandwidth utilization. This efficiency improvement is particularly necessary when communication of compressed voice and video information is involved, because compression tends to make the bit rate variable, in which case the feedback signals enable the network to communicate either the availability of bandwidth or the presence of congestion.
Current traffic management schemes utilize various transmission categories to assign bandwidth in ATM communications. One high priority category is Constant Bit Rate (CBR), in which the transmission is carried out at a constant rate. Two categories of Variable Bit Rate (VBR) transmission are also provided, one for real-time information and another for non-real-time information. A low priority category is Unspecified Bit Rate (UBR), in which data are transmitted by the source with no guarantee of transmission speed. In the recently-developed Available Bit Rate (ABR) service class, feedback from the network nodes, via Resource Management (RM) cells or by way of explicit congestion indications in data cells, is used by the source network node to dynamically control channel transmission rate in response to current network conditions, and within certain transmission parameters that are specified upon opening of the transmission channel (i.e., in the traffic xe2x80x9ccontractxe2x80x9d).
For the ABR class of service, the source and destination nodes agree, in the traffic contract, upon a Peak Cell Rate (PCR) and a Minimum Cell Rate (MCR), thus setting the upper and lower bounds of transmission for an ABR communication. Once these bounds are established, a flow control algorithm is executed, typically both at the source network node and at ATM switches in the network, to define the current transmission rate of each channel. As is known in the art, thousands of connections may be simultaneously open between a given pair of network nodes. As such, traffic management can be a relatively complex operation, especially in controlling ABR category communications.
The setting of upper and lower bounds for ABR traffic is only one issue in ATM flow control. Another issue addressed by ATM flow control schemes, referred to in the art as xe2x80x9cfairnessxe2x80x9d, is the allocation of available bandwidth among the multiple ABR channels that are to be carried by a given link, especially in the case where the available bandwidth is less than the PCR of each of the channels. A proper fairness scheme requires that ABR channels with the highest PCR (or MCR) do not dominate the available bandwidth, and also that the channels with the lowest PCR (or MCR) are not disproportionately served relative to the high data rate channels.
Several fairness criteria are known in the field of ATM flow control. One fairness criterion, referred to as the xe2x80x9cMax-Minxe2x80x9d scheme, is popular as it leads to the maximization of total throughput. This approach is based upon an iterative procedure of computing the cell rate allocation among ABR channels. In a first iteration (l=1) of the procedure, a set variable u1 defines the set of links making up the network, and a set variable v1 defines the set of ABR flows traversing the network. Variable bj is initialized to the bandwidth available to a link Lj in the network, and variable nj is initialized to the number of ABR flows sharing link Lj. During each iteration l, a ratio rl is determined as the smallest ratio bj/nj for all links Ljxcex5ul. A set of links Wl={Lj}ul is then defined as those links for which the ratio bj/nj equals rj, as is a set of flows Sl={Fi}vl where each flow Fi in the set Sl travels over one of the links in Wl. The set Wl establishes the level l bottleneck links, and the set Sl establishes the level l bottleneck flows. The data rate rl is the bottleneck rate of the links in set Wl and is the constraint rate of the flows in set Sl. A reduced network ul+1 is then constructed by subtracting the bottleneck set Wl from the set ul; set vl+1 is then derived, by subtracting set Sl from vl, and defines the set of flows for which constraint rates remain to be determined. Considering m as the number of flows that are both in Sl and which also travel over any link Ljul+1, the construction of the reduced network is completed by subtracting the value mrl from bj, and the number m from nj for each link Ljxcex5ul+1. If the set ul+1 is null, the bottleneck rate of each link and the constraint rate of each flow has been found.
While this approach readily defines the bottleneck and constraint rates, this procedure cannot be directly implemented into ATM network switches because global knowledge of the entire network is required; rather, a practical ATM switch algorithm must permit the links in the network to determine their bottleneck rates in a distributed fashion. A known distributed approach for an individual link Lj of ABR bandwidth Rj, shared by Nj ABR flows, begins by dividing the flows Nj into two subsets: subset Cj containing those flows constrained by another link Lxxe2x89xa0j in the network, and subset Bj of the flows for which link Lj is the bottleneck link. Link Lj is, of course, a bottleneck link at some level k, such that subset Cj contains flows that are constrained at links of bottleneck level 1 through k-1 inclusive. Considering each flow Fi in this subset Cj as having a constraint rate ri, link Lj can then determine the set Cj and the constraint rates ri of its members Fi, and derive its own bottleneck rate BRj as follows:                               BR          j                =                                            R              j                        -                                          ∑                                  i                  ∈                                      C                    j                                                              ⁢                              r                i                                                          "LeftBracketingBar"                                          B                _                            j                        "RightBracketingBar"                                              (        1        )            
According to this arrangement, each link Lj assigns each of the flows in its subset Cj the constraint rates assigned by the other constraining links in the network, and then equally divides the remaining bandwidth among the flows in its subset Bj, effectively assigning the bottleneck rate BRj thereto.
This approach is distributed, in the sense that each link can derive its own bottleneck rate. However, the time complexity of this algorithm is on the order of the square of the number of flows (i.e., O(N2)) which, for large networks, can be quite substantial; the scaling of the network to accommodate more flows is rendered quite costly, given this dependence. Additionally, the memory needs for this approach are also quite substantial, as the ATM switches must maintain the constraint rate for each flow. As such, conventional approaches for simplifying the algorithm both in computational complexity and memory efficiency have been derived.
Charny, et al., xe2x80x9cTime Scale Analysis and Scalability Issues for Explicit Rate Allocation in ATM Networksxe2x80x9d, IEEE/ACM Trans. on Networking (August 1996), pp. 569-581 describes one such simplified distributed algorithm, primarily for determining the subset Cj of flows that are constrained elsewhere from link Lj, by noting that any flow with a constraint rate rl less than the bottleneck rate BRj of link Lj is clearly constrained at a link other than Lj. This approach may be understood by considering a hypothetical sequence of k constraint rates rl, each occurring once in the sequence and arranged in descending order, and each having a tag ml identifying the number of flows having constraint rate rl. One may consider the inequality:                               r                                    l              *                        -            1                          ≥                              R            -                                          ∑                                  l                  =                                      l                    *                                                  k                            ⁢                                                m                  l                                ⁢                                  r                  l                                                                          N            -                                          ∑                                  l                  =                                      l                    *                                                  k                            ⁢                              m                l                                                     greater than                   r                      l            *                                              (        2        )            
where N is the total number of ABR flows (i.e., the sum of ml from l=1 to k) and where R is the total ABR bandwidth. The middle term of inequality (2) thus corresponds to the ratio of the remaining bandwidth of the link (total bandwidth R less the bandwidth occupied by flows constrained elsewhere; i.e., less the flows with lower constraint rates rl, or higher index values as the sequence is arranged in descending order), to the number of remaining ABR flows (total number of flows less the number of flows having higher index constraint rates). According to this simplified distributed approach, inequality (2) is evaluated iteratively in order to find rate rl, which is the smallest rl for which inequality (2) is satisfied. If inequality (2) is satisfied for some l=l*xe2x89xa72, then the link is oversubscribed, and the oversubscribed bottleneck rate BRO is given by:                               BR          O                =                              R            -                                          ∑                                  l                  =                                      l                    *                                                  k                            ⁢                                                m                  l                                ⁢                                  r                  l                                                                          N            -                                          ∑                                  l                  =                                      l                    *                                                  k                            ⁢                              m                l                                                                        (        3        )            
On the other hand, if inequality (2) is not satisfied even for l*=2, the link is under-subscribed, in that sufficient ABR bandwidth is available in the link for all ABR flows. This under-subscribed condition may be represented by:                                           r            1                     less than                                     R              -                                                ∑                                      l                    =                    2                                    k                                ⁢                                                      m                    l                                    ⁢                                      r                    l                                                                                      N              -                                                ∑                                      l                    =                    2                                    k                                ⁢                                  m                  l                                                                    =                                            R              -                                                ∑                                      l                    =                    2                                    k                                ⁢                                                      m                    l                                    ⁢                                      r                    l                                                                                      m              1                                ⇒                                                    ∑                                  l                  =                  1                                k                            ⁢                                                m                  l                                ⁢                                  r                  l                                                       less than             R                                              (        4        )            
In this case, maximization of data rate requires each of the flows passing through his link to be allowed to increase their data rate. According to the conventional distributed algorithm approach, a value for the bottleneck rate BR must be determined that allows the flows to cumulatively increase their rates by amounts that add up to precisely the difference       R    -                  ∑                  l          =          1                k            ⁢                        m          l                ⁢                  r          l                      ,
which is the amount of under-subscription. As described in the above-cited Charny et al. article, lxe2x80x2 is the index such that all flows having a rate rl less than rlxe2x80x2 are constrained at another link in the network; only flows that have rates rl greater than rlxe2x80x2 may thus increase their rates. The bottleneck rate BRU for the under-subscribed case is thus determined from equating the amount of under-subscription to the net proposed increase in data rate:                               R          -                                    ∑                              l                =                1                            k                        ⁢                                          m                l                            ⁢                              r                l                                                    =                                            ∑                              l                =                1                                                              l                  xe2x80x2                                -                1                                      ⁢                                          (                                                      BR                    U                                    -                                      r                    l                                                  )                            ⁢                              m                l                                              =                                                    BR                U                            ⁢                                                ∑                                      l                    =                    1                                                                              l                      xe2x80x2                                        -                    1                                                  ⁢                                  m                  l                                                      -                                          ∑                                  l                  =                  1                                                                      l                    xe2x80x2                                    -                  1                                            ⁢                                                m                  l                                ⁢                                  r                  l                                                                                        (        5        )            
which, in solving for the under-subscribed bottleneck rate BRU, returns:                               BR          U                =                                            R              -                                                ∑                                      l                    =                    1                                    k                                ⁢                                                      m                    l                                    ⁢                                      r                    l                                                              +                                                ∑                                      l                    =                    1                                                                              l                      xe2x80x2                                        -                    1                                                  ⁢                                                      m                    l                                    ⁢                                      r                    l                                                                                                      ∑                                  l                  =                  1                                                                      l                    xe2x80x2                                    -                  1                                            ⁢                              m                l                                              =                                    R              -                                                ∑                                      l                    =                                          l                      xe2x80x2                                                        k                                ⁢                                                      m                    l                                    ⁢                                      r                    l                                                                                      N              -                                                ∑                                      l                    =                                          l                      xe2x80x2                                                        k                                ⁢                                  m                  l                                                                                        (        6        )            
Analysis of expression (6) indicates that smaller values of lxe2x80x2 provide larger values of under-subscribed bottleneck rate BRU; in the trivial case, where lxe2x80x2=1, BRU=∞. In closed-loop ATM flow control and traffic management, the under-subscribed bottleneck rate BRU corresponds to the explicit rate (ER) feedback sent to each source, to serve as an upper bound on the Allowed Cell Rate (ACR) for these channels in the absence of the true constraint rate. Accordingly, this conventional distributed algorithm selects the largest admissible value for BRU, which is given by equation (6) for the case of lxe2x80x2=2:                               BR          U                =                              r            1                    +                                    R              -                                                ∑                                      l                    =                    1                                    k                                ⁢                                                      m                    l                                    ⁢                                      r                    l                                                                                      m              1                                                          (        7        )            
This procedure, according to the conventional distributed algorithm, is useful in ATM flow control implemented according to the Max-Min fair rate allocation type of traffic management. However, it has been observed, in connection with the present invention, that each ATM switch must maintain a full sequence of flow rates, covering all flows communicated through each link. This requirement, of course, requires a large amount of high-speed memory, and involves computational complexity (i.e., processing time) of on the order of N, the total number of flows (i.e., O(N)). Computation of the bottleneck rate of a link itself also requires processing time of O(N), in the worst-case, considering that elements in the sequence of flow rates carried by a link are examined sequentially to determine when inequality (2) is satisfied.
By way of further background, another class of fairness algorithms rely upon approximations to reduce computation time and memory requirements relative to the Min-Max approach, such as described according to the foregoing example. However, these approximating approaches have been observed, in some network configurations, to converge to unfair rate allocations. Other algorithms are known that employ encoded representations of the flow rates, to reduce memory requirements, but these encoded approaches are of course subject to errors resulting from coding inaccuracy.
Furthermore, all approaches that periodically recompute flow rate allocations are subject to problems of improper selection of the recomputation period, similarly as any closed loop feedback control scheme. On one hand, the algorithm is less responsive as the recomputation period is too long, while on the other hand, short recomputation periods can lead to measurement errors and unstable control.
Common to all conventional ABR flow control schemes is the problem of congestion as CBR and VBR connections, as well as additional ABR connections, are added to the network, especially after a period of low bandwidth usage. If the network does not reduce the flow rates of the ABR rates quickly enough, congestion resulting in cell loss can occur. Conversely, low link utilization can result if an upstream ATM switch in the network does not promptly xe2x80x9cinvitexe2x80x9d ABR sources to increase flow rates as bandwidth becomes available. In addition, all switch algorithms should be capable of handling growth in switch queues during transient events; conventional techniques for accomplishing this function includes such operations as requiring source stations to delay rate increases but immediately effect rate decreases, or simply by setting-aside link bandwidth to handle transients; these operations, of course, all reduce link utilization.
It is therefore an object of the present invention to provide an ATM switch, and a method of performing flow control at the same, that implements fairness in ABR rate allocation in a computationally efficient manner.
It is a further object of the present invention to provide such a switch and method with reduced memory requirements.
It is a further object of the present invention to provide such a switch and method that is not subject to coding or approximation errors.
It is a further object of the present invention to provide such a switch and method for which scaling of the number of links, including ABR links, may be readily implemented.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.
The present invention may be implemented in an ATM switch and method of operating the same, to determine the bottleneck rate of each link handled by the switch as the maximum of two arguments: one argument is simply the ratio of the overall ABR bandwidth of the link divided by the number of ABR flows to be communicated by the link, while the other argument corresponds to the highest ABR flow rate plus (or minus) the surplus (or undersupply) bandwidth divided equally among the flows with the highest ABR rate. This bottleneck rate will converge to the exact Max-Min fair rates, over a few measurement intervals. According to the present invention, only the aggregate rate of all flows, the total number of flows, the largest rate, and the number of flows having the largest rate, need be maintained, and may be computed incrementally over a measurement interval, upon one or more flows being new or modified, as indicated by a flag in a memory array corresponding to the flows. According to a preferred embodiment of the invention, two memory arrays are provided for these flags, to permit one array to be used while the other is being updated.